package june6_13;

import datastructures.base.Node;

/**
 * Problem:
	Traverse a binary tree without using any stack or recursion

Morris traversal:
 	Morris traversal is an implementation of in-order traversal that uses threading:
 		1. Create links to the in-order successor
 		2. Print the data using these links
 		3. Revert the changes to restore original tree

Steps:
=====
1. Initialize current as root
2. While current is not null
	if current does not have left child
		- print current data
		- Go to right of the current node
	else
		- find the inorder predecessor - right most node of the left subtree
		if (predecessor's right is null)
			connect predecessor's right to current
		else - predecessor's right is current
			clear the connection
			print current's data
			go to the right of current node
		endif
	endif
   end while
   
Note:
----
 	The tree will be modified during the traversal, it will be reverted back to its original shape after completion
 	No extra space is required for this traversal

 * @author Udhaya
 *
 */
public class MorrisInorderTraversal 
{
	/**
	 * Morris inorder traversal
	 * @param root
	 */
	public static void morrisInorderTraversal (Node root)
	{
		Node current = root;
		
		while (current != null)
		{
			if (current.left == null)
			{
				System.out.print(current.data);
				current = current.right;
			}
			else
			{
				// Find inorder predecessor of current
				Node pre = current.left;
				while (pre.right != null && pre.right != current)
				{
					pre = pre.right;
				}
				// If thread not yet created
				if (pre.right == null)
				{
					pre.right = current;
					current = current.left;
				}
				else	// Revert the changes made, to restore the original tree
						// Fixing the inorder predecessor
				{
					pre.right = null;
					System.out.printf("%d", current.data);
					current = current.right;
				}
			}
		}
	}
	
	public static void main(String[] args) 
	{
		Node root = new Node(1);
		
		root.left	= new Node (2);
		root.right	= new Node (3);
		root.left.left	= new Node (4);
		root.left.right = new Node (5);

		morrisInorderTraversal (root);
		
	}
}
